home *** CD-ROM | disk | FTP | other *** search
/ AOL File Library: 2,801 to 2,900 / aol-file-protocol-4400-2801-to-2900.zip / AOLDLs / C++ Files Library / Graphic Gems I, II & III (C_C++) / Graphics Gems C Code.sea / GemsI / Src / PolyScan / poly_clip.c < prev    next >
Text File  |  1992-06-16  |  4KB  |  131 lines
  1. /*
  2.  * Generic Convex Polygon Scan Conversion and Clipping
  3.  * by Paul Heckbert
  4.  * from "Graphics Gems", Academic Press, 1990
  5.  */
  6.  
  7. /*
  8.  * poly_clip.c: homogeneous 3-D convex polygon clipper
  9.  *
  10.  * Paul Heckbert    1985, Dec 1989
  11.  */
  12.  
  13. #include "poly.h"
  14.  
  15. #define SWAP(a, b, temp)    {temp = a; a = b; b = temp;}
  16. #define COORD(vert, i) ((double *)(vert))[i]
  17.  
  18. #define CLIP_AND_SWAP(elem, sign, k, p, q, r) { \
  19.     poly_clip_to_halfspace(p, q, &v->elem-(double *)v, sign, sign*k); \
  20.     if (q->n==0) {p1->n = 0; return POLY_CLIP_OUT;} \
  21.     SWAP(p, q, r); \
  22. }
  23.  
  24. /*
  25.  * poly_clip_to_box: Clip the convex polygon p1 to the screen space box
  26.  * using the homogeneous screen coordinates (sx, sy, sz, sw) of each vertex,
  27.  * testing if v->sx/v->sw > box->x0 and v->sx/v->sw < box->x1,
  28.  * and similar tests for y and z, for each vertex v of the polygon.
  29.  * If polygon is entirely inside box, then POLY_CLIP_IN is returned.
  30.  * If polygon is entirely outside box, then POLY_CLIP_OUT is returned.
  31.  * Otherwise, if the polygon is cut by the box, p1 is modified and
  32.  * POLY_CLIP_PARTIAL is returned.
  33.  */
  34.  
  35. int poly_clip_to_box(p1, box)
  36. register Poly *p1;
  37. register Poly_box *box;
  38. {
  39.     int x0out = 0, x1out = 0, y0out = 0, y1out = 0, z0out = 0, z1out = 0;
  40.     register int i;
  41.     register Poly_vert *v;
  42.     Poly p2, *p, *q, *r;
  43.  
  44.     /* count vertices "outside" with respect to each of the six planes */
  45.     for (v=p1->vert, i=p1->n; i>0; i--, v++) {
  46.     if (v->sx < box->x0*v->sw) x0out++;    /* out on left */
  47.     if (v->sx > box->x1*v->sw) x1out++;    /* out on right */
  48.     if (v->sy < box->y0*v->sw) y0out++;    /* out on top */
  49.     if (v->sy > box->y1*v->sw) y1out++;    /* out on bottom */
  50.     if (v->sz < box->z0*v->sw) z0out++;    /* out on near */
  51.     if (v->sz > box->z1*v->sw) z1out++;    /* out on far */
  52.     }
  53.  
  54.     /* check if all vertices inside */
  55.     if (x0out+x1out+y0out+y1out+z0out+z1out == 0) return POLY_CLIP_IN;
  56.  
  57.     /* check if all vertices are "outside" any of the six planes */
  58.     if (x0out==p1->n || x1out==p1->n || y0out==p1->n ||
  59.     y1out==p1->n || z0out==p1->n || z1out==p1->n) {
  60.         p1->n = 0;
  61.         return POLY_CLIP_OUT;
  62.     }
  63.  
  64.     /*
  65.      * now clip against each of the planes that might cut the polygon,
  66.      * at each step toggling between polygons p1 and p2
  67.      */
  68.     p = p1;
  69.     q = &p2;
  70.     if (x0out) CLIP_AND_SWAP(sx, -1., box->x0, p, q, r);
  71.     if (x1out) CLIP_AND_SWAP(sx,  1., box->x1, p, q, r);
  72.     if (y0out) CLIP_AND_SWAP(sy, -1., box->y0, p, q, r);
  73.     if (y1out) CLIP_AND_SWAP(sy,  1., box->y1, p, q, r);
  74.     if (z0out) CLIP_AND_SWAP(sz, -1., box->z0, p, q, r);
  75.     if (z1out) CLIP_AND_SWAP(sz,  1., box->z1, p, q, r);
  76.  
  77.     /* if result ended up in p2 then copy it to p1 */
  78.     if (p==&p2)
  79.     bcopy(&p2, p1, sizeof(Poly)-(POLY_NMAX-p2.n)*sizeof(Poly_vert));
  80.     return POLY_CLIP_PARTIAL;
  81. }
  82.  
  83. /*
  84.  * poly_clip_to_halfspace: clip convex polygon p against a plane,
  85.  * copying the portion satisfying sign*s[index] < k*sw into q,
  86.  * where s is a Poly_vert* cast as a double*.
  87.  * index is an index into the array of doubles at each vertex, such that
  88.  * s[index] is sx, sy, or sz (screen space x, y, or z).
  89.  * Thus, to clip against xmin, use
  90.  *    poly_clip_to_halfspace(p, q, XINDEX, -1., -xmin);
  91.  * and to clip against xmax, use
  92.  *    poly_clip_to_halfspace(p, q, XINDEX,  1.,  xmax);
  93.  */
  94.  
  95. void poly_clip_to_halfspace(p, q, index, sign, k)
  96. Poly *p, *q;
  97. register int index;
  98. double sign, k;
  99. {
  100.     register int m;
  101.     register double *up, *vp, *wp;
  102.     register Poly_vert *v;
  103.     int i;
  104.     Poly_vert *u;
  105.     double t, tu, tv;
  106.  
  107.     q->n = 0;
  108.     q->mask = p->mask;
  109.  
  110.     /* start with u=vert[n-1], v=vert[0] */
  111.     u = &p->vert[p->n-1];
  112.     tu = sign*COORD(u, index) - u->sw*k;
  113.     for (v= &p->vert[0], i=p->n; i>0; i--, u=v, tu=tv, v++) {
  114.     /* on old polygon (p), u is previous vertex, v is current vertex */
  115.     /* tv is negative if vertex v is in */
  116.     tv = sign*COORD(v, index) - v->sw*k;
  117.     if (tu<=0. ^ tv<=0.) {
  118.         /* edge crosses plane; add intersection point to q */
  119.         t = tu/(tu-tv);
  120.         up = (double *)u;
  121.         vp = (double *)v;
  122.         wp = (double *)&q->vert[q->n];
  123.         for (m=p->mask; m!=0; m>>=1, up++, vp++, wp++)
  124.         if (m&1) *wp = *up+t*(*vp-*up);
  125.         q->n++;
  126.     }
  127.     if (tv<=0.)        /* vertex v is in, copy it to q */
  128.         q->vert[q->n++] = *v;
  129.     }
  130. }
  131.